public class Solution1139 {
    public int largest1BorderedSquare(int[][] grid) {
        int[][] f=new int[grid.length][grid[0].length];
        for (int i=0;i<grid.length;i++){
            int last=0;
            for (int j=grid[0].length-1;j>=0;j--){
                if (grid[i][j]==0){
                    last=0;
                }else {
                    last++;
                }
                f[i][j]=last;
            }
        }
        int[][] g=new int[grid.length][grid[0].length];
        for (int i=0;i<grid[0].length;i++){
            int last=0;
            for (int j=grid.length-1;j>=0;j--){
                if (grid[j][i]==0){
                    last=0;
                }else {
                    last++;
                }
                g[j][i]=last;
            }
        }
        int ans=0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                for (int k=f[i][j];k>0;k--){
                    if (g[i][j]>=k && g[i][j+k-1]>=k && f[i+k-1][j]>=k){
                        ans=Math.max(ans,k);
                        break;
                    }
                }
            }
        }
        return ans*ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1139().largest1BorderedSquare(new int[][]{{1,1,1},{1,0,1},{1,1,1}}));
    }
}
